A note on “axioms” for computational complexity and computation of finite functions

Recent studies of computational complexity have focused on “axioms” which characterize the “difficulty of a computation” (Blum, 1967a or the measure of the “size of a program,” (Blum, 1967b and Pager, 1969). In this paper we wish to carefully examine the consequences of hypothesizing a relation which connects measures of size and of difficulty of computation. The relation is motivated by the fact that computations are performed “a few instructions at a time” so that if one has a bound on the difficulty of a computation, one also has a bound on the “number of executed instructions.” This relation enables one to easily show that algorithms exist for finding the most efficient programs for computing finite functions. This result, which has been obtained independently for certain Turing machine measures by David Pager, contrasts sharply with results for measures of size, where it is known that no algorithm can exist for going from a finite function to the shortest program for computing it (Blum, 1967b) (Pager, 1969). In a concluding section, which can be read independently of the above-mentioned results, some remarks are made about the desirability of using a program for computing an infinite function when one is interested in the function only on some finite domain. There is nothing deep in this paper, and we hope that a reader familiar with the rudiments of recursion theory will find this paper a simple introduction to the “axiomatic” theory of computational complexity. Such a reader might do well to begin with the concluding remarks after reading the basic definitions